package com.example.sorts12.sorts;

/**
 * 快速排序
 * @auther lijiewei
 * @date 2021/8/27 17:34
 */
public class QuickSort {

    /**
     * 快速排序
     * @param a 数组
     * @param n 数组长度
     * @return
     * @author lijiewei
     * @date   2021/8/27 17:38
     */
    public static void quickSort(int[] a, int n) {
        quickSortinternally(a, 0, n-1);
    }

    /**
     * 快速排序递归函数
     * @param a 数组
     * @param p 开始下标
     * @param r 结束下标
     * @return
     * @author lijiewei
     * @date   2021/8/27 17:38
     */
    private static void quickSortinternally(int[] a, int p, int r) {
        if (p >= r) {
            return;
        }
        //求分区点
        int q = partition(a, p, r);
        quickSortinternally(a, p, q-1);
        quickSortinternally(a, q+1, r);
    }

    /**
     * 获取分区点
     * @param a 数组
     * @param p 开始下标
     * @param r 结束下标
     * @return
     * @author lijiewei
     * @date   2021/8/27 17:43
     */
    private static int partition(int[] a, int p, int r) {
        //分区数值
        int pivot = a[r];
        //i左边为小于pivot，i右边为大于等于pivot
        int i=p;
        for (int j = p; j < r; j++) {
            if (a[j] < pivot) {
                if (i != j) {
                    int tmp = a[i];
                    a[i] = a[j];
                    a[j] = tmp;
                }
                i++;
            }
        }
        int tmp = a[i];
        a[i] = a[r];
        a[r] = tmp;
        return i;
    }
}
